package 左哥算法.ch10暴力递归;
import java.util.Scanner;

public class ch03传纸条 {
    public static void main(String[] args) {
//        Scanner sc=new Scanner(System.in);
//        int[][] arr=new int[sc.nextInt()][sc.nextInt()];
//        for (int[] ints : arr) {
//            for (int i = 0; i < ints.length; i++) {
//                ints[i]=sc.nextInt();
//            }
//        }
        int[][] arr={
                {0,4,9},
                {99,100,101},
                {5,7,0},
        };
        System.out.println(fun(arr, 0, 0, false));
    }

    /**
     * @param arr：位置图
     * @param row：所在行
     * @param col：所在列
     * @param isOver：是否走完一轮
     * @return：走该节点能拿到的最大值
     */
    public static int fun(int[][] arr,int row,int col,boolean isOver){
        if (col+row==0&&isOver){    //第二次回到起点
            return 0;
        }
        if (row==arr.length-1&&col==arr[0].length-1&&!isOver){  //第一次来到右下角的情况
            return fun(arr,row,col,true);   //走到右下角后改变策略
        }
        int temp=arr[row][col];
        if (row+col!=0&&(row+1!=arr.length||col+1!=arr[0].length)){   //非起点或终点时
            arr[row][col]=Integer.MIN_VALUE;    //标志该节点已经走过
        }
        if (isOver){    //已经走过一轮
            int toUp=Integer.MIN_VALUE,toLeft=Integer.MIN_VALUE;
            if(col>0&&arr[row][col-1]>=0){
                toLeft = fun(arr, row, col-1, isOver);
            }
            if (row>0&&arr[row-1][col]>=0){
                toUp = fun(arr, row-1, col, isOver);
            }
            arr[row][col]=temp;     //回溯到未走过的状态
            return Math.max(toUp,toLeft)+temp;
        }else{  //还未走过一轮
            int toDown=Integer.MIN_VALUE,toRight=Integer.MIN_VALUE;
            if(col<arr[0].length-1&&arr[row][col+1]>=0){
                toRight = fun(arr, row, col+1, isOver);
            }
            if (row<arr.length-1&&arr[row+1][col]>=0){
                toDown = fun(arr, row+1, col, isOver);
            }
            arr[row][col]=temp;     //回溯到未走过的状态
            return Math.max(toDown,toRight)+temp;
        }
    }
}
